home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_200 / 289_01 / buildlvl.c < prev    next >
Text File  |  1989-05-23  |  14KB  |  431 lines
  1. /*-----------------------------------------------------------------------------
  2. Build the tree of moves down to a given level.
  3.  
  4. Revision History
  5. ----------------
  6. NAME            DATE            MODS
  7. Gary Culp       19 Dec 1988 -
  8.                  2 Jan 1988     Initial version
  9. -----------------------------------------------------------------------------*/
  10. #include <stdio.h>
  11. #include "othello.h"
  12.  
  13. STATIC int after_opponents_move(move_type humans_move);
  14.  
  15. STATIC void build_children_of_a_board(
  16.    key_type parent_limb_key,
  17.    key_type parent_board_key,
  18.    unsigned char movers_color);
  19.  
  20. STATIC int build_a_level(void);
  21.  
  22. /* return values from build_a_level() */
  23. #define BT_COMPLETED  0
  24. #define BT_DBFULL     1
  25.  
  26. /*
  27.    This level:
  28.  
  29.    board/limb  has children?  is bottom?
  30.    -------------------------------------
  31.   -limb----------n--------------n------------ERROR
  32.   -limb----------n------------y--------------ERROR
  33.    limb        y                n         descend along each child
  34.    limb        y              y           return
  35.    board         n              n         build children
  36.    board         n            y           return
  37.   -board-------y----------------n------------ERROR
  38.    board       y              y           return
  39. */
  40.  
  41.  
  42. /*
  43. Keep track of the depth to which the tree has been fully built.
  44. */
  45. STATIC int tree_depth = 0;
  46.  
  47. /*
  48. The build_tree function is iterative rather than recursive because building the
  49. tree is asynchronous to the human's move; and we want to take advantage of
  50. information about the human's move immediately (by pruning moves he didn't
  51. make from the tree).
  52.  
  53. Information for manually-recursive tree build:
  54.    'stack' of limb keys
  55.    desired depth (actually use value of stack index at desired depth; which
  56.       turns out to be the desired depth - 2)
  57.    stack pointer for stack of limb keys (actually an index rather than
  58.       a pointer)
  59.    mover's color at current depth
  60. */
  61. STATIC key_type limb_key_stack[BT_MAX_DEPTH];
  62. STATIC int bt_desired_nest;
  63. STATIC int bt_current_nest; /* "stack pointer" (index) for limb_key_stack */
  64. STATIC unsigned char bt_movers_color;
  65.  
  66. STATIC int human_state;
  67. /* defines for human_state */
  68. #define HS_NOT_HUMANS_TURN    0
  69. #define HS_WAITING_FOR_HUMAN  1
  70. #define HS_HUMAN_MOVED        2
  71.  
  72. STATIC humans_move_limb_key;
  73.  
  74.  
  75. /*
  76. Build the tree to the specified level
  77.  
  78. The function builds the tree until it reaches the specified depth, or
  79. the database fills up.
  80.  
  81. If movers_color == THEM_PIECE:
  82.    The function will also check for input from the human player while it is
  83.    building the tree.  If it has to stop building the tree, it will continue
  84.    to check for the human's input.  It will not return until the human player
  85.    has input his move.
  86. If movers_color == US_PIECE:
  87.    The function will not check for input from the human player.
  88.  
  89. This function assumes that the root of the tree corresponds to the current
  90. state of the board.
  91.  
  92. Returns:
  93.    depth to which tree was completely built
  94. */
  95. int
  96. build_tree(int depth_to_build, unsigned char movers_color)
  97. {
  98.    struct limb_struct far *limb_ptr;
  99.    int temp;
  100.  
  101.    if (movers_color == THEM_PIECE) {
  102.       human_state = HS_WAITING_FOR_HUMAN;
  103.       depth_to_build++; /* We'll delete 1 level after the human moves; so we
  104.                            build an extra level now. */
  105.    }
  106.    else {
  107.       human_state = HS_NOT_HUMANS_TURN;
  108.    }
  109.  
  110.    limb_ptr = db_retrieve_limb(curnt_top_limb);
  111.    if (limb_ptr->move & BOARD_MASK) {
  112.       /* The root is a board.  There is a lower-level function
  113.          (after_opponents_move()) which assumes that the root is not a board,
  114.          so we have to build the first level of the tree before continuing.
  115.       */
  116.       build_children_of_a_board(curnt_top_limb,
  117.                                 limb_ptr->bc.board_key,
  118.                                 movers_color);
  119.       tree_depth = 1;
  120.    }
  121.  
  122.    for (bt_desired_nest = tree_depth - 1;
  123.         bt_desired_nest <= depth_to_build - 2;
  124.         bt_desired_nest++)
  125.    {
  126.       limb_key_stack[0] = limb_ptr->bc.child_key;
  127.       bt_current_nest = 0;
  128.       bt_movers_color = movers_color ^ (US_PIECE | THEM_PIECE);
  129.  
  130.       /* Try to build a level. If the database fills up but we're waiting for
  131.          input from the human, keep trying to build until we get his input.
  132.       */
  133.       do {
  134.          temp = build_a_level();
  135.       } while (temp != BT_COMPLETED && human_state == HS_WAITING_FOR_HUMAN);
  136.  
  137.       if (temp == BT_COMPLETED) {
  138.          tree_depth = bt_desired_nest + 2;
  139.       }
  140.       else {
  141.          break;
  142.       }
  143.    }
  144.  
  145.    /* We may finish building the tree to the depth we desire before the
  146.       human opponent enters his move.  If this happens, this loop will wait
  147.       for him to enter his move.
  148.    */
  149.    while (human_state == HS_WAITING_FOR_HUMAN) {
  150.       move_type humans_move;
  151.  
  152.       if ((humans_move = check_for_input()) != HASNT_MOVED) {
  153.          human_state = HS_HUMAN_MOVED;
  154.          after_opponents_move(humans_move);
  155.       }
  156.    }
  157.  
  158.    if (movers_color == THEM_PIECE) {
  159.  
  160.       free_limb(curnt_top_limb);   /* delete root limb */
  161.  
  162.       /* Make limb for human's move the new root limb */
  163.       curnt_top_limb = humans_move_limb_key;
  164.  
  165.       tree_depth--;  /* Since we deleted the old root, the tree is shallower */
  166.    }
  167.    return (tree_depth);
  168. }
  169.  
  170.  
  171. /*
  172. Build another level onto the tree
  173. This function communicates through static variables.
  174.  
  175. Returns:
  176.    BT_COMPLETED: finished building the level
  177.    BT_DBFULL:    had to stop building because database was almost full
  178. */
  179. STATIC int
  180. build_a_level()
  181. {
  182.    limb_type far *limb_ptr;
  183.    move_type humans_move;
  184.  
  185.    while (1) {       /* exit from loop by 'return's */
  186.       if (human_state == HS_WAITING_FOR_HUMAN  &&
  187.           (humans_move = check_for_input()) != HASNT_MOVED)
  188.       {
  189.          human_state = HS_HUMAN_MOVED;
  190.          if (after_opponents_move(humans_move)) {
  191.             return (BT_COMPLETED);
  192.          }
  193.       }
  194.  
  195.       /*
  196.       If the database is almost full, stop building.
  197.       Resume build at this point later on, after the tree has been trimmed.
  198.       */
  199.       if (db_almost_full()) {
  200.          return (BT_DBFULL);
  201.       }
  202.  
  203.       /* Limbs have either a board or children.
  204.          If this limb has a board, build its children now.
  205.       */
  206.  
  207.       limb_ptr = db_retrieve_limb(limb_key_stack[bt_current_nest]);
  208.  
  209.       if (limb_ptr->move & BOARD_MASK) {  /* it's a board */ 
  210.          build_children_of_a_board(limb_key_stack[bt_current_nest],
  211.                                  limb_ptr->bc.board_key,
  212.                                  bt_movers_color);
  213.       }
  214.  
  215.       /*
  216.          Figure out next limb key to examine (leave on top of limb_key_stack)
  217.       */
  218.       if (bt_current_nest != bt_desired_nest) {
  219.          /* Follow child key to nest down one level */
  220.          limb_key_stack[bt_current_nest + 1] =
  221.             db_retrieve_limb(limb_key_stack[bt_current_nest])->bc.child_key;
  222.          ++bt_current_nest;
  223.          bt_movers_color ^= (US_PIECE | THEM_PIECE);
  224.       }
  225.       else {
  226.          while (bt_current_nest >= 0) {   /* also contains a 'break' */
  227.             /* 
  228.                Replace limb key on top of stack with its next sibling;
  229.                if it has no next sibling, pop it off the stack.
  230.             */
  231.             if (
  232.                 (limb_key_stack[bt_current_nest] =
  233.                  db_retrieve_limb(limb_key_stack[bt_current_nest])->sibling_key
  234.                 )
  235.                 == NO_KEY
  236.                )
  237.             {
  238.                --bt_current_nest;  /* pop stack */
  239.                bt_movers_color ^= (US_PIECE | THEM_PIECE);
  240.             }
  241.             else {
  242.                break; /* exit from loop */
  243.             }
  244.          }
  245.  
  246.          if (bt_current_nest < 0) {
  247.             /* a complete level of the tree has been built */
  248.             return (BT_COMPLETED);
  249.          }
  250.       }
  251.    }
  252. }
  253.  
  254.  
  255. /*
  256. Build all the child boards for a given parent_limb.
  257. The parent_limb must have a board (not child limbs) associated with it.
  258. */
  259. STATIC void
  260. build_children_of_a_bo